package main

import "fmt"

/*
寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。


示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 */


// 合并两个有序数组
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	l1, l2, p := len(nums1) - 1, len(nums2) - 1, len(nums1) + len(nums2) - 1
	res := make([]int, p + 1)
	// 倒序比较两个数组， 合并在第一个数组上
	for l1 >=0 && l2 >= 0 {
		if nums1[l1] > nums2[l2] {
			res[p] = nums1[l1]
			p --
			l1 --
		}else if nums1[l1] < nums2[l2] {
			res[p] = nums2[l2]
			p --
			l2 --
		}else{
			res[p] = nums1[l1]
			res[p - 1] = nums2[l2]
			p = p - 2
			l1 --
			l2 --
		}
	}
	if l1 >= 0 {
		for l1 >= 0 {
			res[p] = nums1[l1]
			p --
			l1 --
		}
	}
	if l2 >= 0 {
		for l2 >= 0 {
			res[p] = nums2[l2]
			p --
			l2 --
		}
	}
	//fmt.Println(res)
	// 计算中位数
	resl := len(res)
	temp := resl / 2
	if resl % 2 != 0 {
		return float64(res[temp])
	}else {
		return float64(float64((res[temp] + res[temp - 1])) / 2.0)
	}
}

func main() {
	fmt.Println(findMedianSortedArrays([]int{2,2,4,4}, []int{2,2,4,4}))
}
